// https://leetcode.cn/problems/house-robber/

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        int n = nums.size();
        vector<int> res(n + 1);
        res[0] = 0;
        res[1] = nums[0];
        for (int i = 2; i <= n; ++i) {
            res[i] = max(res[i - 2] + nums[i - 1], res[i - 1]);
        }
        return res.back();
    }
};

// 空间优化
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        int n = nums.size();
        int pre = 0;
        int cur = nums[0];
        for (int i = 2; i <= n; ++i) {
            int tmp = max(pre + nums[i - 1], cur);
            pre = cur;
            cur = tmp;
        }
        return cur;
    }
};